package tree

type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}

func New(value int) *Tree {
	return &Tree{Value: value}
}

func Sample(k int) *Tree {
	// 随机生成一个二叉树，包含10个元素，依次为 k, 2*k, 3*k, ..., 10*k
	l := []int{}
	for i := 1; i < 10; i++ {
		l = append(l, k*i)
	}
	return createTree(l)
}

// 根据前序遍历的数组，生成一个结构随机的二叉树
func createTree(l []int) *Tree {

	if len(l) == 0 {
		return nil
	}
	if len(l) == 1 {
		return &Tree{Value: l[0]}
	}

	// 随机选择一个位置作为根节点
	mid := len(l) / 2
	root := &Tree{Value: l[mid]}

	// 递归创建左右子树
	root.Left = createTree(l[:mid])
	if mid+1 < len(l) {
		root.Right = createTree(l[mid+1:])
	}

	return root
}
